There are two basic methods of drawing lines on a discrete integer mesh, such as the pixel array of a computer display. In drawing lines on an integer mesh, a step between points in the line is always made in the major direction (a horizontal step in the first octant) and the only decision to be made by the line draw engine is whether to also make a step in the minor direction (a vertical step in the first octant) thereby resulting in a diagonal step. In order to draw a line in this fashion, most line draw circuitry employs either a Bresenham engine or a DDA (Digital Differential Analyzer) engine.
A Bresenham line draw engine 10 is illustrated in FIG. 1. The Bresenham line draw engine comprises line draw logic 12 coupled to an adder 14. An initial error value, E0, is loaded into the accumulator of the adder 14. Constants K1 and K2 are computed prior to drawing the line, and input to the Bresenham line draw logic 12. For each step in the major direction, the line draw logic 12 determines whether a step in the minor direction should also be made. Hence, for a first octant lines, the Bresenham line draw engine determines whether a horizontal step is made or whether a upwardly diagonal step is made. If a horizontal (major) step is made, then K1 is added to the error in the accumulator. If a diagonal (major and minor) step is made, then K2 is added to the error in the adder 14. The Bresenham line draw logic 12 determines whether to make a major axis or diagonal step based on the sign of the error term stored in the accumulator of the adder 14.
A DDA line, on the other hand, uses fractional arithmetic. The DDA line draw engine typically comprises an accumulator for the integer and fraction approximation of the slope. Because binary arithmetic requires that fractions be represented in a finite number of bits, a DDA line may suffer from accumulated error.
Most graphics boards with line draw capabilities employ either a Bresenham or a DDA line draw engine. In many cases, it is desirable to have capability of drawing both Bresenham and DDA lines. For example, Bresenham lines assume integer end-points. For non-integer end-point lines, the Bresenham algorithm does not give the best matched pixels with the ideal line. DDA lines can handle arbitrary end-points, but require a significant number of fractional bits to achieve the precision of a Bresenham line. Generally, it is easier to implement anti-aliasing and shading with DDA lines than with Bresenham lines.
Therefore, a need has arisen in the industry for a line draw engine capable of producing both Bresenham and DDA lines.